//#include <iostream>
//using namespace std;
//
//class Date {
//private:
//    int _year;
//    int _month;
//    int _day;
//    static const int MonthDay[];
//public:
//    Date(int year, int month = 1, int day = 1)
//        : _year(year)
//        , _month(month)
//        , _day(day)
//    {}
//
//    inline bool isLeapYear(int year) const {
//        return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0);
//    }
//
//    inline int GetMonthDays(int year, int month) const {
//        if (month == 2 && isLeapYear(_year)) {
//            return 29;
//        }
//        return MonthDay[month - 1];
//    }
//
//    Date AfterYearDays(int day) {
//        while (day > GetMonthDays(_year, _month)) {
//            day -= GetMonthDays(_year, _month);
//            ++_month;
//            if (_month == 13) {
//                _month = 1;
//                ++_year;
//            }
//        }
//        _day = day;
//        return *this;
//    }
//
//    friend ostream& operator<<(ostream& out, Date& d) {
//
//        if (d._month <= 9) {
//            if (d._day <= 9) {
//                cout << d._year << '-' << '0' << d._month << '-' << '0' << d._day;
//            }
//            else {
//                cout << d._year << '-' << '0' << d._month << '-' << d._day;
//            }
//        }
//        else {
//            if (d._day < 9) {
//                cout << d._year << '-' << d._month << '-' << '0' << d._day;
//            }
//            else {
//                cout << d._year << '-' << d._month << '-' << d._day;
//            }
//        }
//        return out;
//    }
//
//};
//
//const int Date::MonthDay[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//
//int main() {
//    int n;
//    int year, month, day;
//    int days;
//
//    cin >> n;
//    for (int i = 0; i < n; ++i)
//    {
//        cin >> year >> month >> day >> days;
//        Date a(year, month, day);
//        a.AfterYearDays(days);
//        cout << a << endl;
//    }
//
//    return 0;
//}
//
//#include <stdlib.h>
//#include <stdio.h>
//#include <string>
//int globalVar = 1;
//
//static int staticGlobalVar = 1;
//
//void main()
//
//{
//
//	static int staticVar = 1;
//
//	int localVar = 1;
//
//
//
//	int num1[10] = { 1, 2, 3, 4 };
//
//	char char2[] = "abcd";
//
//	const char* pChar3 = "abcd";
//
//	int* ptr1 = (int*)malloc(sizeof(int) * 4);
//
//	int* ptr2 = (int*)calloc(4, sizeof(int));
//
//	int* ptr3 = (int*)realloc(ptr2, sizeof(int) * 4);
//
//	free(ptr1);
//
//	free(ptr3);
//
//	printf("%d", strlen(pChar3));
//
//}
//
//
//#include <iostream>  
//#include <vector>  
//#include <algorithm>  
//#include <cmath>  
//#include <climits>  
//
//// ������������һ����ά����  
//const double distances[14][14] = {
//    {0, 4.1, 1.9, 2.5, 4.1, 4.6, 2.6, 0.087, 5.1, 4.8, 4.7, 5.1, 3.6, 1.6},
//        {4.1, 0, 6.2, 6.8, 3.2, 2.1, 6.5, 5.2, 1, 1.7, 1.4, 9.2, 5.2, 3.2},
//    {1.9,	6.2,	0,	0.769,	5.5,	6,	3.6,	1.8,	7.2,	6.6,	7.3,	3.4,	4.6,	3.8 },
//{2.5,	6.8,	0.769,	0,	5.5,	5.9,	3.4,	2.5,	7.9,	6.7,	7.2,	3.3,	4.4,	4.5 },
//{4.1,	3.2,	5.5,	5.5,	0,	2.2,	4.9,	4.2,	3.5,	1.8,	2.4,	7.8,	4.6,	2.8 },
//{4.6,	2.1,	6,	5.9,	2.2,	0,	5.3,	4.6,	2.4,	0.704,	1.3,	8.2,	5.1,	3.7 },
//{2.6,	6.5,	3.6,	3.4,	4.9,	5.3,	0,	2.6,	7.4,	6.8,	6.6,	2.4,	1.2,	4 },
//{0.087,	5.2,	1.8,	2.5,	4.2,	4.6,	2.6,	0,	6.2,	5.3	,5.9	,5.1	,3.6,	2.8 },
//{5.1,	1	,7.2,	7.9	,3.5,	2.4	,7.4	,6.2,	0	,1.7	,1.2	,10	,6.2,	4.3 },
//{4.8	,1.7,	6.6,	6.7	,1.8	,0.704	,6.8,	5.3	,1.7,	0	,0.762	,8.9,	5.2,	3.3 },
//{4.7,	1.4	,7.3,	7.2	,2.4,	1.3	,6.6,	5.9,	1.2,	0.762,	0	,9.6	,5.9,	4 },
//{5.1,	9.2	,3.4	,3.3	,7.8	,8.2	,2.4	,5.1	,10	,8.9	,9.6,	0	,4.1	,6.9 },
//{3.6,	5.2	,4.6	,4.4	,4.6	,5.1	,1.2	,3.6	,6.2	,5.2	,5.9	,4.1,	0	,2.9 },
//{1.6,	3.2	,3.8	,4.5	,2.8	,3.7	,4	,2.8	,4.3	,3.3	,4	,6.9,	2.9	,0 },
//};
//
//// �����洢��ǰ·�����ܾ���  
//double currentDistance = INT_MAX;
//// �����洢���·��������  
//std::vector<int> shortestPath;
//
//// �����������������·�����ܾ���  
//double calculatePathDistance(const std::vector<int>& path) {
//    double total = 0;
//    for (size_t i = 0; i < path.size() - 1; ++i) {
//        total += distances[path[i]][path[i + 1]];
//    }
//    // ����ʱ��Ҫ�ص���㣬���Լ��ϻص����ľ���  
//    total += distances[path.back()][path[0]];
//    return total;
//}
//
//// �����������������п��ܵ�·������  
//void generatePermutations(std::vector<int>& current, std::vector<bool>& visited, int n) {
//    if (current.size() == n) {
//        // ���������Ϊ���һ�������γɱջ�  
//        current.push_back(0); // ���轨ƽ����ũó�г�������0  
//        double pathDistance = calculatePathDistance(current);
//        if (pathDistance < currentDistance) {
//            currentDistance = pathDistance;
//            shortestPath = current;
//        }
//        current.pop_back(); // �Ƴ����ӵ����  
//        return;
//    }
//
//    for (int i = 0; i < n; ++i) {
//        if (!visited[i]) {
//            visited[i] = true;
//            current.push_back(i + 1); // ����������1��ʼ  
//            generatePermutations(current, visited, n);
//            current.pop_back();
//            visited[i] = false;
//        }
//    }
//}
//
//int main() {
//    std::vector<int> current;
//    std::vector<bool> visited(13, false); // ������13���㣨��������㣩  
//
//    // ������1��ʼ����Ϊ��㽨ƽ����ũó�г�������0  
//    current.push_back(1);
//    generatePermutations(current, visited, 13);
//
//    // ������·���;���  
//    std::cout << "Shortest path distance: " << currentDistance << std::endl;
//    std::cout << "Shortest path: ";
//    for (size_t i = 0; i < shortestPath.size(); ++i) {
//        std::cout << shortestPath[i] << " ";
//    }
//    std::cout << "0" << std::endl; // �ص���㽨ƽ����ũó�г�  
//
//    return 0;
//}
//
//#include <stdio.h>
//#include <stdlib.h>
//#include <time.h>
//
//int main()
//{
//	int a[10] = { 1,5,6,3,9,7,4,5,10,3 };
//
//	int max = a[0]; // ��Ϊ���ֵ�����������Ҫô�ǵ�һ����Ҫô���ǵ�һ����
//	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
//	{
//		if (max < a[i])
//		{
//			max = a[i];
//		}
//	}
//
//	printf("%d", max);
//
//	return 0;
//}
//
//#include <iostream>
//
//class A
//{
//private:
//	int a;
//public:
//	A(const int& other)
//	{
//		a = other;
//	}
//
//	operator int()
//	{
//		return (int)a;
//	}
//};
//
//void f(int x, A y)
//{
//	;
//}
//
//void f(A x, int y)
//{
//	;
//}
//
//int main()
//{
//	int x(0);
//	A y(0);
//
//	f(x, x);
//	f(y, y);
//
//	return 0;
//}

//#include <iostream>
//using namespace std;
//
//class A
//{
//private:
//	int _a;
//public:
//	A(int other = 0)
//	{
//		_a = other;
//	}
//
//	void Print()
//	{
//		std::cout << _a;
//	}
//
//	operator int() const
//	{
//		return _a;
//	}
//
//	operator long long() const
//	{
//		return _a;
//	}
//
//	void f(A x, A y)
//	{
//		cout << "void f(A x, A y)" << endl;
//	}
//
//	void f(long long x, A y)
//	{
//		cout << "void f(long long x, A y)" << endl;
//	}
//};
//
//int main()
//{
//	A a(3);
//	int b = 3;
//
//	a.f(a, a);
//	a.f(b, b);
//
//	a.f(a, b);
//	a.f(b, a);
//
//
//	return 0;
//}
//

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main()
//{
//	vector<int> c(3,1);
//	cout << c.size() << endl;
//
//	return 0;
//}

//#include <iostream>  
//#include <queue>  
//
//class MyStack {
//private:
//    std::queue<int> q1, q2;
//
//    // Helper function to transfer elements from one queue to another  
//    void transfer(std::queue<int>& from, std::queue<int>& to) {
//        while (!from.empty()) {
//            to.push(from.front());
//            from.pop();
//        }
//    }
//
//public:
//    /** Initialize your data structure here. */
//    MyStack() = default;
//
//    /** Push element x onto stack. */
//    void push(int x) {
//        q1.push(x);
//    }
//
//    /** Removes the element on top of the stack and returns that element. */
//    int pop() {
//        if (q1.empty()) {
//            return -1; // or throw an exception  
//        }
//
//        // Leave one element in q1 and transfer others to q2  
//        while (q1.size() > 1) {
//            q2.push(q1.front());
//            q1.pop();
//        }
//
//        int top = q1.front();
//        q1.pop();
//
//        // Swap the roles of q1 and q2  
//        std::swap(q1, q2);
//
//        return top;
//    }
//
//    /** Get the top element. */
//    int top() {
//        if (q1.empty()) {
//            return -1; // or throw an exception  
//        }
//
//        // Similar to pop, but we return the last element without removing it  
//        while (q1.size() > 1) {
//            q2.push(q1.front());
//            q1.pop();
//        }
//
//        int top = q1.front();
//
//        // Push back the element to q1 and swap the roles of q1 and q2  
//        q2.push(top);
//        std::swap(q1, q2);
//
//        return top;
//    }
//
//    /** Returns whether the stack is empty. */
//    bool empty() {
//        return q1.empty();
//    }
//};
//
//int main() {
//    MyStack stack;
//    stack.push(1);
//    stack.push(2);
//    stack.push(3);
//    stack.push(4);
//    stack.push(5);
//
//    stack.pop();
//    stack.pop();
//    stack.pop();
//
//
//    return 0;
//}

//class A
//{
//public:
//	int val;
//	A(int v)
//		:val(v)
//	{}
//};
//
//int main()
//{
//	A a(10);
//	a.val;
//	return 0;
//}

//#include <iostream>
//#include <vector>
//
//template <class T>
//class martix
//{
//private:
//	std::vector<T> _data;
//	std::vector<size_t> _dim;
//};

//#include <iostream>  
//#include <cstdio> // Ϊ��ʹ�� printf  
//
//class A
//{
//public:
//    int _a = 0;
// 
//    A(int a = 10)
//    {
//        _a = a;
//    }
//};
//
//int main()
//{
//    A a; // ���� _a ������ʼ��Ϊ 10  
//    printf("%d", a._a); // Ӧ�ô�ӡ�� 10  
//    return 0;
//}

//#include <iostream>
//using namespace std;
//
//class A
//{
//public:
//	int _a;
//
//	A(int a = 0)
//	{
//		cout << "A(int a = 0)" << endl;
//	}
//	A(const A& r)
//	{
//		cout << "A(const A& r)" << endl;
//	}
//	A& operator=(const A& r)
//	{
//		cout << " operator=(A& r)" << endl;
//	}
//	~A()
//	{
//		cout << "~A()" << endl;
//	}
//};
//
//
//int main()
//{
//	A b(1);
//
//	return 0;
//}

//#include <stdexcept>  
//#include <iostream>  
//#include <vector>  
//#include <random>  
//using namespace std;
//
//// ʹ�����������ͷֲ�����������ĺ���  
//double get_random(double min_value, double max_value, bool is_integer)
//{
//    // ��֤��Сֵ�����ֵ����Ч��  
//    if (min_value > max_value)
//    {
//        throw std::invalid_argument("��Сֵ���ܴ������ֵ");
//    }
//
//    // ������������棬ʹ������豸��Ϊ����  
//    std::random_device rd;
//    std::mt19937 gen(rd());
//
//    // �����Ƿ�����ѡ���ʵ��ķֲ�  
//    if (is_integer)
//    {
//        // ��������ֵ��ʹ��std::uniform_int_distribution  
//        std::uniform_int_distribution<> dis(static_cast<int>(min_value), static_cast<int>(max_value));
//        return dis(gen);
//    }
//    else
//    {
//        // ���ڸ�����ֵ��ʹ��std::uniform_real_distribution  
//        std::uniform_real_distribution<> dis(min_value, max_value);
//        return dis(gen);
//    }
//}
//
//int main()
//{
//    vector<unsigned long long> a;
//    // ����������ķ�Χ  
//    double min_value = 0;
//    double max_value = 10000;
//    bool is_integer = true;  
//
//    for (unsigned long long i = 0; i < (unsigned long long)1e6; ++i)
//    {
//        // ʹ��get_random������䣬��ȷ��ת��Ϊunsigned long long  
//        a.push_back(static_cast<unsigned long long>(get_random(min_value, max_value, is_integer)));
//    }
//
//    // ��ӡ vector �е�һЩԪ������֤  
//    for (size_t i = 0; i < 100; ++i)
//    {
//        cout << a[i] << endl;
//    }
//
//    return 0;
//}

//#include <vector>  
//#include <stdexcept>  
//#include <iostream>  
//
//class str 
//{
//private:
//    std::vector<signed char> _data;
//    size_t _size;
//    size_t _capacity;
//
//    void updateSizeAndCapacity() 
//    {
//        _size = _data.size();
//        _capacity = _data.capacity();
//    }
//
//public:
//    str() : _size(0), _capacity(0) {}
//
//    str(size_t n, signed char a) {
//        _data.resize(n, a);
//        updateSizeAndCapacity();
//    }
//
//    template<typename Iterator>
//    str(Iterator begin, Iterator end) {
//        for (auto it = begin; it != end; ++it) {
//            _data.push_back(static_cast<signed char>(*it));
//        }
//        updateSizeAndCapacity();
//    }
//
//    str(const str& other) : _data(other._data) {
//        updateSizeAndCapacity();
//    }
//
//    str(str&& other) noexcept : _data(std::move(other._data)) {
//        updateSizeAndCapacity();
//    }
//
//    str& operator=(const str& other) {
//        if (this == &other)
//            return *this;
//        _data = other._data;
//        updateSizeAndCapacity();
//        return *this;
//    }
//
//    str& operator=(str&& other) noexcept {
//        if (this == &other)
//            return *this;
//        _data = std::move(other._data);
//        updateSizeAndCapacity();
//        return *this;
//    }
//
//    signed char& operator[](size_t index) {
//        if (index >= _size)
//            throw std::out_of_range("����������Χ");
//        return _data[index];
//    }
//
//    const signed char& operator[](size_t index) const {
//        if (index >= _size)
//            throw std::out_of_range("����������Χ");
//        return _data[index];
//    }
//
//    class iterator {
//    public:
//        using iterator_type = typename std::vector<signed char>::iterator;
//        iterator_type it;
//
//        iterator(iterator_type it) : it(it) {}
//
//        iterator& operator++() { ++it; return *this; }
//        iterator operator++(int) { iterator tmp = *this; ++(*this); return tmp; }
//        signed char& operator*() const { return *it; }
//        bool operator==(const iterator& other) const { return it == other.it; }
//        bool operator!=(const iterator& other) const { return it != other.it; }
//    };
//
//    class const_iterator {
//    public:
//        using iterator_type = typename std::vector<signed char>::const_iterator;
//        iterator_type it;
//
//        const_iterator(iterator_type it) : it(it) {}
//
//        const_iterator& operator++() { ++it; return *this; }
//        const_iterator operator++(int) { const_iterator tmp = *this; ++(*this); return tmp; }
//        const signed char& operator*() const { return *it; }
//        bool operator==(const const_iterator& other) const { return it == other.it; }
//        bool operator!=(const const_iterator& other) const { return it != other.it; }
//    };
//
//    iterator begin() { return iterator(_data.begin()); }
//    iterator end() { return iterator(_data.end()); }
//    const_iterator begin() const { return const_iterator(_data.begin()); }
//    const_iterator end() const { return const_iterator(_data.end()); }
//
//    size_t size() const { return _size; }
//    size_t capacity() const { return _capacity; }
//
//    void clear() {
//        _data.clear();
//        updateSizeAndCapacity();
//    }
//
//    void append(const str& other) {
//        _data.insert(_data.end(), other.begin().it, other.end().it);
//        updateSizeAndCapacity();
//    }
//
//    str& operator+=(const str& other) {
//        append(other);
//        return *this;
//    }
//
//    str& operator+=(signed char c) {
//        _data.push_back(c);
//        updateSizeAndCapacity();
//        return *this;
//    }
//
//    bool operator<(const str& other) const {
//        return _data < other._data;
//    }
//
//    bool operator<=(const str& other) const {
//        return _data <= other._data;
//    }
//
//    bool operator>(const str& other) const {
//        return _data > other._data;
//    }
//
//    bool operator>=(const str& other) const {
//        return _data >= other._data;
//    }
//
//    bool operator==(const str& other) const {
//        return _data == other._data;
//    }
//
//    bool operator!=(const str& other) const {
//        return !(*this == other);
//    }
//
//    friend std::istream& operator>>(std::istream& is, str& str) {
//        str.clear();
//        char ch;
//        while (is.get(ch) && ch != '\n') {
//            str._data.push_back(static_cast<signed char>(ch));
//        }
//        str.updateSizeAndCapacity();
//        return is;
//    }
//
//    friend std::ostream& operator<<(std::ostream& os, const str& str) {
//        for (auto ch : str._data) {
//            os << static_cast<char>(ch);
//        }
//        return os;
//    }
//};
//
//int main() {
//    str s1(5, 'a');
//    str s2(s1);
//    s2 += s1;
//    std::cout << s2 << std::endl;
//
//    s2 += 'b';
//    std::cout << s2 << std::endl;
//
//    str s3(s2.begin(), s2.end());
//    std::cout << s3 << std::endl;
//
//    str s4, s5;
//    std::cout << "�������һ���ַ���: ";
//    std::cin >> s4;
//    std::cout << "������ڶ����ַ���: ";
//    std::cin >> s5;
//
//    if (s4 == s5) {
//        std::cout << "�����ַ������" << std::endl;
//    }
//    else if (s4 < s5) {
//        std::cout << "��һ���ַ���С�ڵڶ����ַ���" << std::endl;
//    }
//    else {
//        std::cout << "��һ���ַ������ڵڶ����ַ���" << std::endl;
//    }
//
//    return 0;
//}

//#include<iostream>
//
//class A {};
//
//int f(A& a)
//{
//	return 1;
//}
//
//int main()
//{
//	const A a;
//	printf("%d", f(a));
//}


// #include <iostream>  
// #include <vector>  
// #include <cstdlib>  
// #include <ctime>  
// #include <chrono>  
// #include <algorithm>  

// // ѡ���������  
// void selectionInsertionSort(std::vector<int>& arr) {
//     int n = arr.size();
//     for (int i = 1; i < n; ++i) {
//         int minIdx = i;
//         for (int j = i + 1; j < n; ++j) {
//             if (arr[j] < arr[minIdx]) {
//                 minIdx = j;
//             }
//         }
//         std::swap(arr[i], arr[minIdx]);
//     }
// }

// // ����ѡ���������  
// void binarySelectionInsertionSort(std::vector<int>& arr) {
//     int n = arr.size();
//     for (int i = 1; i < n; ++i) {
//         int key = arr[i];
//         int left = 0, right = i - 1;
//         // ���ֲ��Ҳ���λ��  
//         while (left <= right) {
//             int mid = left + (right - left) / 2;
//             if (arr[mid] > key) {
//                 right = mid - 1;
//             }
//             else {
//                 left = mid + 1;
//             }
//         }
//         // ����Ԫ��  
//         for (int j = i - 1; j >= left; --j) {
//             arr[j + 1] = arr[j];
//         }
//         arr[left] = key;
//     }
// }

// // �����������  
// std::vector<int> generateRandomArray(int size, int minVal, int maxVal) {
//     std::vector<int> arr(size);
//     for (int i = 0; i < size; ++i) {
//         arr[i] = rand() % (maxVal - minVal + 1) + minVal;
//     }
//     return arr;
// }

// int main() {
//     srand(static_cast<unsigned int>(time(0)));

//     const int size = 100000;
//     const int minVal = 0;
//     const int maxVal = 1000000;

//     std::vector<int> arr1 = generateRandomArray(size, minVal, maxVal);
//     std::vector<int> arr2 = generateRandomArray(size, minVal, maxVal);

//     // ѡ���������  
//     auto start1 = std::chrono::high_resolution_clock::now();
//     selectionInsertionSort(arr1);
//     auto end1 = std::chrono::high_resolution_clock::now();
//     std::chrono::duration<double> duration1 = end1 - start1;

//     // ����ѡ���������  
//     auto start2 = std::chrono::high_resolution_clock::now();
//     binarySelectionInsertionSort(arr2);
//     auto end2 = std::chrono::high_resolution_clock::now();
//     std::chrono::duration<double> duration2 = end2 - start2;

//     std::cout << "ѡ�����������ʱ: " << duration1.count() << " ��" << std::endl;
//     std::cout << "����ѡ�����������ʱ: " << duration2.count() << " ��" << std::endl;

//     return 0;
// }


#include <iostream>